#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N=1000005;
LL a[40];
int flag[4*N];
int idx;

struct Node
{
    LL f[2];
    LL mx[2];
    LL mn[2];
    int size;
    bool operator<(const Node& s)const
    { return f[idx]<s.f[idx]; }
}A[N],B[N],tr[4*N];

void update(int i)
{
    int s=1;
    if(flag[i<<1])
    {
        for(int k=0;k<=1;k++)
        {
            if(tr[i<<1].mn[k]<tr[i].mn[k]) tr[i].mn[k]=tr[i<<1].mn[k];
            if(tr[i<<1].mx[k]>tr[i].mx[k]) tr[i].mx[k]=tr[i<<1].mx[k];
        }
        s+=tr[i<<1].size;
    }
    if(flag[i<<1|1])
    {
        for(int k=0;k<=1;k++)
        {
            if(tr[i<<1|1].mn[k]<tr[i].mn[k]) tr[i].mn[k]=tr[i<<1|1].mn[k];
            if(tr[i<<1|1].mx[k]>tr[i].mx[k]) tr[i].mx[k]=tr[i<<1|1].mx[k];
        }
        s+=tr[i<<1|1].size;
    }
    tr[i].size=s;
}

void build(int l,int r,int i,int deep) 
{
    if(l>r) return;
    int mid=(l+r)>>1;
    idx=deep;
    flag[i]=1;
    flag[i<<1]=0; flag[i<<1|1]=0;

    nth_element(B+l,B+mid,B+r+1);
    for(int k=0;k<=1;k++)
       tr[i].mx[k]=tr[i].mn[k]=tr[i].f[k]=B[mid].f[k];

    build(l,mid-1,i<<1,1-deep);
    build(mid+1,r,i<<1|1,1-deep);
    update(i);
}
int check(LL x1,LL y1,LL x2,LL y2)
{
    if(x1*x2+y1+y2>=0) return 1;
    return 0;
}
int count(Node p,int i)
{
    int re=0;
    re+=check(tr[i].mn[0],tr[i].mn[1],p.f[0],p.f[1]);
    re+=check(tr[i].mn[0],tr[i].mx[1],p.f[0],p.f[1]);
    re+=check(tr[i].mx[0],tr[i].mn[1],p.f[0],p.f[1]);
    re+=check(tr[i].mx[0],tr[i].mx[1],p.f[0],p.f[1]);
    return re;
}
int query(Node p,int i)
{
    if(!flag[i]) return 0;
    if(count(p,i)==4) return tr[i].size;
    int re=check(p.f[0],p.f[1],tr[i].f[0],tr[i].f[1]);
    if(count(p,i<<1)) re+=query(p,i<<1);
    if(count(p,i<<1|1)) re+=query(p,i<<1|1);
    return re;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
          scanf("%lld",&a[i]);
        int mid=n/2;
        int tt=(1<<mid);
        int tot1=0,tot2=0;
        for(int i=0;i<=tt-1;i++)
        {
            A[tot1].f[0]=0;
            A[tot1].f[1]=0;
            for(int k=1;(1<<(k-1))<tt;k++)
            {
                if((1<<(k-1))&i)
                {
                    A[tot1].f[1]+=A[tot1].f[0]*a[k];
                    A[tot1].f[0]+=a[k];
                }
            }
            tot1++;
        }
        int tt2=1<<n;
        for(int i=0;i<tt2;i+=tt)
        {
            B[tot2].f[0]=0;
            B[tot2].f[1]=0;
            for(int k=mid+1;(1<<(k-1))<tt2;k++)
            {
                if((1<<(k-1))&i)
                {
                    B[tot2].f[1]+=B[tot2].f[0]*a[k];
                    B[tot2].f[0]+=a[k];
                }
            }
            tot2++;
        }
        /*for(int i=0;i<tot1;i++)
        cout<<A[i].f[0]<<" "<<A[i].f[1]<<endl;
        cout<<"-----------------"<<endl;
        for(int i=0;i<tot2;i++)
        cout<<B[i].f[0]<<" "<<B[i].f[1]<<endl;*/
        build(0,tot2-1,1,0);
        int ans=-1;
        for(int i=0;i<tot1;i++)
        {
            ans+=query(A[i],1);
        }
        printf("%d\n",ans);
    }
    return 0;
}